
const operatorPriorityMap = {
  ["|"]: 1,
  ["·"]: 2,
  ["?"]: 3,
  ["+"]: 3,
  ["*"]: 3
};
// 为正则表达式添加连接符·
const insertExplicitConcatOperator = (exp)  =>{
  let output = "";
  for (let i = 0; i < exp.length; i++) {
    const token = exp[i];
    output +=token
    if(token === "(" || token === "|"){
      continue;
    }
    if(i<exp.length - 1){
      const lookahead = exp[i+1];
      if(lookahead === "*" ||
      lookahead === ")" ||
      lookahead === "|"){
        continue
      }
      output += "·";
    }
  }
  return output;
}

// console.log(insertExplicitConcatOperator("ab?+"))

const peek = (stack) =>{
  return stack.length && stack[stack.length - 1]
};
/**
 * 中缀表达式转换后缀表达式
 *  初始化一个栈，用于保存暂时含不能确定运算顺序的运算符。
    从左到右处理各个元素，直到末尾。可能遇到三种情况：
    ① 遇到操作数。直接加入后缀表达式
    ② 遇到界限符。遇到`(` 直接入栈；遇到`)`则依次弹出栈内运算符并加入后缀表达式，直到弹出`(`为止。注意：`(`不加入后缀表达式。
    ③ 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到`(`或栈空则停止。之后再把当前运算符入栈。
    按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。
 */
const infixToPostfix = (exp) =>{
  //  a·(b·c)*
  /**
   *  ["|"]: 1,
      ["·"]: 2,
      ["?"]: 3,
      ["+"]: 3,
      ["*"]: 3
   */
  let output = "";
  const stack = [];
  for (const token of exp) {
    if(token ===")"){
      while(peek(stack) !== "("){
        output += stack.pop();
      }
      stack.pop();
    }else if(token === "·" || token === "|" || token === "*"){
      while(operatorPriorityMap[peek(stack)] && 
      operatorPriorityMap[peek(stack)] >= operatorPriorityMap[token]){
        output += stack.pop();
      }
      stack.push(token)
    }else if(token === "("){
      stack.push(token)
    }else{
      output += token;
    }
  }

  while(stack.length){
    output += stack.pop();
  }
  return output;
}

